#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>

typedef struct NODE
{
	int info;
	int degree;
	struct NODE* parent;
	struct NODE* child;
	struct NODE* sibling;
}NODE;

// prototip

NODE* CREATE_BHEAP(); // creaza arborele binomial
NODE* CREATE_BNODE(int); // creaza un nod pentru arbore

void DELETE_BNODE(NODE*,int);


void LINK_BNODE(NODE* , NODE*); // leaga nodurile in arbore
void REVERT_NODE(NODE* );
void DECREASE_KEY(NODE*, int, int);
void DISPLAY(NODE*);
void EXTRACT_MIN(NODE*);

NODE* FIND_BNODE(NODE*, int);
NODE* MERGE_BHEAP(NODE* , NODE*);
NODE* UNION_BHEAP(NODE* , NODE*);
NODE* INSERT_BHEAP(NODE* , NODE*);
NODE* MIN_BHEAP(NODE*);


// functie

NODE* CREATE_BHEAP()
{
	NODE* temp;
	temp = NULL;
	return temp;
}
NODE* CREATE_BNODE(int info)
{
	NODE* temp = new NODE; // NODE* temp; temp = (NODE*)malloc(sizeof(NODE));
	temp->info = info; // temp->info == (*temp).info
	return temp;
}
void DELETE_BNODE(NODE* root,int i)
{
	/*if(root == NULL)
	{
		printf("HEAP gol");
	}*/
	if(root!=NULL) 
	{
		DECREASE_KEY(root,i,-1000);
		//printf("Stergere efectuata");
	}
}

void LINK_BNODE(NODE* n1, NODE* n2)
{
	n1->parent = n2;
	n1->sibling = n2->child;
	n2->child = n1;
	n2->degree = n2->degree++;
}
void REVERT_BNODE(NODE* root, NODE* temp)
{
	if(temp->sibling != NULL)
	{
		REVERT_BNODE(root, temp->sibling);
		(temp->sibling)->sibling = temp;
	}
	else root = temp;
}
void DECREASE_KEY(NODE* root, int i, int k) //i cheia veche, k cheia noua
{
	int temp;
	NODE* p, *temp2, *temp3;

	p=FIND_BNODE(root,i);

	if(p == NULL)
	{
		//printf("Cheia nu exista\n");
	}
	else
	{
		if( k > p->info)
		{
			printf("Cheia noua este mai mare decat cheia actuala\n");
		}

		p->info = k;
		temp2 = p;
		temp3 = p->parent;

		while(temp3 != NULL && temp2->info < temp3->info)
		{
			temp = temp2->info;
			temp2->info = temp3->info;
			temp3->info = temp;
			temp2 = temp3;
			temp3 = temp3->parent;
		}
		printf("Cheia a fost schimbata cu succes!");
	}
}
void DISPLAY(NODE* root)
{
	if(root == NULL)
		printf("HEAP gol");
	else
	{
		if( root != NULL )
		{
			DISPLAY( root->sibling);
			printf("%d",root->info);
			DISPLAY( root->child);
		}
	}
}
void EXTRACT_MIN(NODE* root)
{
	if(root==NULL)
		return;
	NODE* min = MIN_BHEAP(root);
	DELETE_BNODE(root,min->info);
}


NODE* FIND_BNODE(NODE* root, int info) 
{
	NODE* temp = root;
	NODE* p = NULL;

	if(temp->info == info)
	{
		p = temp;
		return p;
	}

	if(temp->child != NULL && p == NULL)
		p=FIND_BNODE(temp->child, info);

	if(temp->sibling != NULL && p == NULL)
		p=FIND_BNODE(temp->sibling, info);

	return p;
}
NODE* MERGE_BHEAP(NODE* bheap1, NODE* bheap2)
{
	NODE* root = CREATE_BHEAP();
	NODE* temp1, *temp2, *aux;

	temp1 = bheap1;
	temp2 = bheap2;

	if(temp1 != NULL)
	{
		if(temp2 != NULL && temp1->degree < temp2->degree )
		{
			root = temp1;
		}
		else if(temp2 != NULL && temp1->degree > temp2->degree )
		{
			root = temp2;
		}
		else root = temp1;
	}
	else root = temp2;

	while(temp1 != NULL && temp2 != NULL)
	{
		if(temp1->degree < temp2->degree)
			temp1 = temp1->sibling;
		else if (temp1->degree == temp2->degree)
		{
			aux = temp1->sibling;
			temp1->sibling = temp2;
			temp1 = aux;
		}
		else 
		{
			aux = temp2->sibling;
			temp2->sibling = temp1;
			temp2 = aux;
		}
	}
	return root;
}
NODE* UNION_BHEAP(NODE* temp1, NODE* temp2)
{
	NODE* root = CREATE_BHEAP();
	root = MERGE_BHEAP(temp1, temp2);

	if(root == NULL) return root;
	NODE* next_temp, *prev_temp, *temp;

	prev_temp = NULL;
	temp = root;
	next_temp = temp->sibling;

	while(next_temp != NULL )
	{
		if((temp->degree != next_temp->degree) || ((next_temp->sibling != NULL) && (next_temp->sibling)->degree == temp->degree))
		{
			prev_temp = temp;
			temp = next_temp;
		}
		else
		{
			if( temp->info <= next_temp->info)
			{
				temp->sibling = next_temp->sibling;
				LINK_BNODE(next_temp,temp);
			}
			else 
			{
				if(prev_temp == NULL)
					root = next_temp;
				else prev_temp->sibling = next_temp;
				LINK_BNODE(temp,next_temp);
				temp=next_temp;
			}
		}
		next_temp = temp->sibling;
	}
	return root;
}
NODE* INSERT_BHEAP(NODE* root, NODE* temp)
{
	NODE* root1 = CREATE_BHEAP();

	temp->parent = NULL;
	temp->child = NULL;
	temp->sibling = NULL;
	temp->degree = 0;
	root1 = temp;

	root = UNION_BHEAP(root, root1);
	return root;
}
NODE* MIN_BHEAP(NODE* root) //h1
{
	if(root==NULL)
		return NULL;

	NODE* root1 = CREATE_BHEAP(); //
	root1=root;
	NODE* temp_min = root1; //x
	int min=root1->info;
	while (root1->sibling)
	{
		if (min>root1->sibling->info)
		{
			temp_min=root1->sibling;
			min=root1->sibling->info;
		}
		root1=root1->sibling;
	}
	return temp_min;
}

void show(NODE *root, int* k,char** ret)
{
	if (root)
	{
		if (root->parent)
			sprintf(ret[*k],"%s (%d->%d)",ret[*k],root->parent->info,root->info);
		else
		sprintf(ret[*k],"%s (%d->%d)",ret[*k],root->info,0);

		if (root->child)
		{
			*k=*k+1;
			show(root->child,k,ret);
		}
		if (root->sibling)
		{
		//	*k=*k+1;
			show(root->sibling,k,ret);
		}
	}
}

void showv2(NODE*root,int *x, int y, char**ret)
{
	
	ret[*x][y] ='|';
	ret[*x][y+1]='_';
	ret[*x][y+2]='_';
	ret[*x][y+3]='_'; 
	
	if (root)
		sprintf(ret[*x]+y+4," %d ",root->info);
		//ret[x][y+2]=root->info;
	else return;

	if (root->child) 
	{
		*x=*x+1;
		showv2(root->child,x,y+6,ret);
	}
	if (root->sibling)
	{
		*x=*x+2;
		showv2(root->sibling,x,y,ret);
	}
}

void work(char** buf, int k)
{
	for (int j=1; j<100; j++)
		for (int i=1; i<100; i++)
		{
			if ((buf[i][j]=='|'))
			{
				for (int q=i+1; q<100; q++)
					if ((buf[q][j]=='|') )
						if (buf[q-1][j-3] != '_')
						for (int w=i+1; w<q; w++)
							buf[w][j]='|';
						else
						q=100;


			}
		}
}
